Run Ends Format Description

The run ends format is a specialized variant of run length encoding. Run length encoding relies on the fact that certain types of images frequently contain parts where many adjacent pixels share the same color. A description of such an occurrence is known as a run. Typically a run is described as 1) a color, and 2) the number of following pixels that are that color. An image raster (or entire image) can be stored as a collection of runs. For example, an image of this page could be described as "2000 white pixels, 5 black pixels, 15 white pixels, 5 black pixels, 15 white pixels, 5 black pixels, 30 white pixels" and so on.

Since the run ends format only works on 1-bit images, it can take advantage of the fact that there are only two possible colors present in the raster: 0 and 1. Since there are only two possible colors, the color does not need to be stored for each run. It is inferred from the previous run. Also, having only two colors makes it especially likely that long runs of identically colored pixels will occur, as compared to images with more colors present.

The following points characterize the run ends format:

An image is stored as a collection of rasters encoded in run ends format. Each raster is independent - there is no information shared between rasters. Therefore, consider only a single raster when thinking about the run ends format.
A run ends raster is stored as an array of run ends. A run end is a value of type AT_RUN which marks the end of a run by storing the horizontal position (X-coordinate) of where the next run begins.
Run ends are stored in order from left to right.
It is always assumed that the first run in a raster is white. If it is not, there will be a "null run" at the beginning of the raster which ends at column 0. This is a means of getting the first real (non-zero-length) run to be black.
The last run end in the raster is always equal to the image width. This value is stored three times to mark the end of the raster.

Here are some examples of rasters that are 8 pixels in width. Each raster is shown first in uncompressed format, then in run ends format as it would be stored in memory on a 32-bit x86 platform. That is, the number 5 is stored in memory as "05 00 00 00".

Example 1	Example 2
11001000 02 00 00 00 // white run until column 2 04 00 00 00 // black run until column 4 05 00 00 00 // white run until column 5 08 00 00 00 // done (remainder is black) 08 00 00 00 08 00 00 00	00000101 00 00 00 00 // get first run to be black 05 00 00 00 // black run until column 5 06 00 00 00 // white run until column 6 07 00 00 00 // black run until column 7 08 00 00 00 // done (remainder is white) 08 00 00 00 08 00 00 00